//给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。
//
// 题目数据保证答案符合 32 位带符号整数范围。
//
//
//
// 示例 1：
//
//
//输入：s = "rabbbit", t = "rabbit"
//输出：3
//解释：
//如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
//rabbbit
//rabbbit
//rabbbit
//
// 示例 2：
//
//
//输入：s = "babgbag", t = "bag"
//输出：5
//解释：
//如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。
//babgbag
//babgbag
//babgbag
//babgbag
//babgbag
//
//
//
//
// 提示：
//
//
// 1 <= s.length, t.length <= 1000
// s 和 t 由英文字母组成
//
//
// Related Topics 字符串 动态规划 👍 1001 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function numDistinct(s: string, t: string): number {

    /**
     dp[i][j]: s前i个字符，t前j个字符，s子序列中t出现的个数
     dp[0][0]=1, 表示s前0个字符为''，t前0个字符为''
     当s[i - 1] 与 t[j - 1]相等时，dp[i][j]可以有两部分组成。
     一部分是用s[i - 1]来匹配，那么个数为dp[i - 1][j - 1]。即不需要考虑当前s子串和t子串的最后一位字母，所以只需要 dp[i-1][j-1]。
     一部分是不用s[i - 1]来匹配，个数为dp[i - 1][j]。
     例如： s：bagg 和 t：bag ，s[3] 和 t[2]是相同的，但是字符串s也可以不用s[3]来匹配，即用s[0]s[1]s[2]组成的bag。
     当然也可以用s[3]来匹配，即：s[0]s[1]s[3]组成的bag。
     当s[i - 1] 与 t[j - 1]不相等时，dp[i][j]只有一部分组成，不用s[i - 1]来匹配（就是模拟在s中删除这个元素），即：dp[i - 1][j]
     */
    const sLen: number = s.length,
        tLen: number = t.length;
    const dp: number[][] = new Array(sLen + 1).fill(0)
        .map(_ => new Array(tLen + 1).fill(0));
    for (let m = 0; m < sLen; m++) {
        dp[m][0] = 1;
    }
    for (let i = 1; i <= sLen; i++) {
        for (let j = 1; j <= tLen; j++) {
            if (s[i - 1] === t[j - 1]) {
                //? 使用s[i - 1]来匹配和不使用s[i - 1]来匹配的情况
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
            } else {
                //? 那肯定是不能使用s[i - 1]来匹配
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[sLen][tLen];
};
//leetcode submit region end(Prohibit modification and deletion)
